The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.
A computer network is a set of computing components interconnected by communication links. Each computing component may be a separate computing device, such as, without limitation, a hub, switch, bridge, router, server, gateway, or personal computer, or a component thereof. Each computing component, or “network device,” is considered to be a node within the network. A communication link is a mechanism of connecting at least two nodes such that each node may transmit data to and receive data from the other node. Such data may be transmitted in the form of signals over transmission media such as, without limitation, electrical cables, optical cables, or wireless media.
The structure and transmission of data between nodes is governed by a number of different protocols. There may be multiple layers of protocols, typically beginning with a lowest layer, such as a “physical” layer that governs the transmission and reception of raw bit streams as signals over a transmission medium. Each layer defines a data unit (the protocol data unit, or “PDU”), with multiple data units at one layer combining to form a single data unit in another. Additional examples of layers may include, for instance, a data link layer in which bits defined by a physical layer are combined to form a frame or cell, a network layer in which frames or cells defined by the data link layer are combined to form a packet, and a transport layer in which packets defined by the network layer are combined to form a TCP segment or UDP datagram. The Open Systems Interconnection model of communications describes these and other layers of communications. However, other models defining other ways of layering information may also be used. The Internet protocol suite, or “TCP/IP stack,” is one example of a common group of protocols that may be used together over multiple layers to communicate information. However, techniques described herein may have application to other protocols outside of the TCP/IP stack.
A given node in a network may not necessarily have a link to each other node in the network, particularly in more complex networks. For example, in wired networks, each node may only have a limited number of physical ports into which cables may be plugged in to create links. Certain “terminal” nodes—often servers or end-user devices—may only have one or a handful of ports. Other nodes, such as switches, hubs, or routers, may have a great deal more ports, and typically are used to relay information between the terminal nodes. The arrangement of nodes and links in a network is said to be the topology of the network, and is typically visualized as a network graph or tree.
A given node in the network may communicate with another node in the network by sending data units along one or more different “paths” through the network that lead to the other node, each path including any number of intermediate nodes. The transmission of data across a computing network typically involves sending units of data, such as packets, cells, or frames, along paths through intermediary networking devices, such as switches or routers, that direct or redirect each data unit towards a corresponding destination.
While a data unit is passing through an intermediary networking device—a period of time that is conceptualized as a “visit” or “hop”—the device may perform any of a variety of actions with the data unit. The exact set of actions taken will depend on a variety of characteristics of the data unit, such as metadata found in the header of the data unit, and in many cases the context or state of the network device. For example, address information specified by or otherwise associated with the data unit, such as a source address, destination address, or path information, is typically used to determine how to handle a data unit (i.e. what actions to take with respect to the data unit). For instance, an Internet Protocol (“IP”) data packet may include a destination IP address field within the header of the IP data packet, based upon which a network router may determine one or more other networking devices, among a number of possible other networking devices, to forward the IP data packet to.
The information used by such networking devices to determine how to handle data units based on address information is generally referred to herein as forwarding information. The address information is collectively referred to herein as a “forwarding table” or “policy table.” A table may associate an address with policy or rule information that dictates the action(s) that the device is to perform with respect to any data unit that is associated with the address. A network device may be configured to consult different types of forwarding tables for different purposes. For instance, a device may include one table describing policies to apply based on source address information at one network layer, another table describing policies to apply based on destination address information at another network layer, and yet other tables that serve yet other purposes. Note that the term “forwarding table” is a term of convenience, and does not require that the forwarding information actually be stored as a table. That is, though the forwarding information is perhaps easiest to conceptualize in table form, a forwarding table may actually be represented in a variety of forms, such as explained in later sections.
Rather than including a separate record, or entry, for each possible address, a table may be configured such that some entries of the table, or even all entries of the table, specify policy information for different groups of addresses. For example, an entry in an IP-based forwarding table may specify a group of IP addresses and a “next hop” device identifier, indicating that any data unit specifying a destination address that is a part of the specified group of IP addresses is to be forwarded to the specified next hop device. Each group may be referred to as a “subnet.”
One common manner of specifying a group of addresses is by a common prefix that each of the addresses shares. Generally, a prefix is a first portion of a data item, such as of a network address. A prefix may be of any length, and thus any given address may have, or “match,” multiple prefixes. For example, the prefixes 192, 192.168, and 192.168.1 would all be valid prefixes for the address 192.168.1.1. A table that maps prefixes to other information, such as forwarding instructions, is referred to herein as a prefix table. A forwarding table may thus be implemented as a prefix table.
Many types of network devices process a significant number of data units on a nearly continuous basis. Thus, the speed at which networking devices are able to process received data units can be of great importance. For these reasons and others, forwarding information and other similar data may be stored in a networking device using specialized high-speed memory components, such as content addressable memory (CAM). However, the use of such high-speed memory in networking devices is relatively expensive, both in terms of cost and power consumption. Thus, more efficient techniques for storing and searching forwarding information are desirable, particularly as the number of forwarding entries stored by a networking device grows large.